package com.guang.guiji.sort;

import java.util.Random;

public class QuickSort {
	public void quickSort(int a[], int start, int end) {
		if (start < end) {
			int i = start;
			int j = end;
			int temp = a[i];
			while (i < j) {
				while ((i < j) && (a[j] >= temp)) {
					j--;
				}
				if (i < j) {
					a[i] = a[j];
					i++;
				}
				while ((i < j) && (a[i] <= temp)) {
					i++;
				}
				if (i < j) {
					a[j] = a[i];
					j--;
				}
			}

			quickSort(a, start, i - 1);
			quickSort(a, i + 1, end);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long startTime = System.currentTimeMillis();// 返回以毫秒为单位的当前时间，即程序开始时间
		int[] a = new int[1000000];
		Random random = new Random();
		for (int i = 0; i < a.length; i++) {
			//a[i] = random.nextInt(10);//出错
			a[i] = random.nextInt(a.length);
		}
		QuickSort qs = new QuickSort();
		qs.quickSort(a, 0, a.length - 1);
		
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}

		long entTime = System.currentTimeMillis();// 返回以毫秒为单位的当前时间，即程序结束时间
		System.out.println((entTime - startTime) / 1000 + "s");// 打印程序运行时间
		
	}

}
